#include <iostream>
#include <vector>
#include <string>
using namespace std;
class Solution {
public:
    vector<vector<string>> solveNQueens(int n) {
        vector<vector<string>>result;
        vector<string>board(n, string(n, '.'));
        backtrack(n,0,result, board);
        return result;
    }
private:
    void backtrack(int n, int row, vector<vector<string>>& result, vector<string>& board) {
        if (row == n) { result.push_back(board); return; }
        for (int col = 0; col < n; col++) {
            if (isvalid(row, col, board, n)) {
                board[row][col] = 'Q';
                backtrack(n, row + 1, result, board);
                board[row][col] = '.';
            }
        }
    }
        bool isvalid(int row,int col,vector<string>board,int n) {
            for (int i = 0; i < row; i++) { if (board[i][col] == 'Q') { return false; } }
            for (int i = 0; i < col; i++) { if (board[row][i] == 'Q') { return false; } }
            for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {
                if (board[i][j] == 'Q') {
                    return false;
                }
            }
            for (int i = row - 1, j = col + 1; i >= 0 && j < n; i--, j++) {
                if (board[i][j] == 'Q') {
                    return false;
                }
            }
            return true;
    }
    
};
